#pragma once

//Fibonacci数列类
class Fib {
//f = fib(k - 1), g = fib(k)。
private:
    long f;
private:
    long g;
public:
    //初始化为不小于n的最小Fibonacci项
    Fib(int n) {
        f = 1;
        g = 0;
        while (g < n) next();
    }

    //获取当前Fibonacci项，O(1)时间
    int get() { return g; }

    //转至下一Fibonacci项，O(1)时间
    int next() {
        g += f;
        f = g - f;
        return g;
    }

    //转至上一Fibonacci项，O(1)时间
    int prev() {
        f = g - f;
        g -= f;
        return g;
    }
};